#include<vector>
using namespace std;
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() < 1) return 0;
        vector<int>tails(nums.size());
        int len = 0;
        tails[len] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (tails[len] < nums[i]) tails[++len] = nums[i];
            else {
                int left = 0, right = len;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (tails[mid] >= nums[i]) right = mid - 1;
                    else left = mid + 1;
                }
                tails[left] = nums[i];
            }
        }
        return len + 1;
    }
};

//int main() {
//    Solution sol;
//    vector<int>nums = { 10,9,2,5,3,4 };
//    sol.lengthOfLIS(nums);
//}